Move generation in chess engines

Move generation

Definition

Move generation is the process of enumerating all moves available to the side to move in a given chess position. In computer chess, it typically refers to creating a list of moves for search, either as all legal moves (that do not leave one’s king in check) or as pseudo-legal moves (that obey piece movement rules but may leave the king in check) followed by a legality filter.

How it’s used in chess and engines

For chess engines, move generation is the front door to the entire search: every node in the game tree begins by generating moves. Efficient, correct move generation enables fast search (millions of positions per second) and accurate evaluation. For human players, the related idea is “candidate move generation” — systematically listing promising options (often with the CCT heuristic: checks, captures, threats) before deeper calculation.

Legal vs. pseudo-legal moves

• Legal moves: obey piece rules and leave one’s king unexposed; include special moves (castling, en passant, promotion) only when their additional conditions are satisfied.
• Pseudo-legal moves: obey movement rules but may ignore king safety. Engines often generate pseudo-legal moves first (fast), then test each move by making it and verifying that the king is not in check (filtering).

Special attention is required for:

• Castling: the king must not be in check, must not pass through or land on attacked squares, and the path must be clear.
• En passant: the capture is legal only if, after removing the captured pawn from the board, your king is still safe. This subtlety frequently exposes generator bugs.
• Pins and discovered checks: moves by pinned pieces are legal only if they remain on the pin line or capture the pinning piece.
• Check evasions: if in check, only king moves, captures of the checking piece, or interpositions (for a single sliding check) are legal; in double check, only king moves are legal.

Implementation techniques (engine-centric)

• Board representations:
  • Bitboards: 64-bit masks for sets of squares; extremely fast with modern CPUs. Popular in engines like Glaurung/Stockfish.
  • Mailbox (e.g., 0x88 or 10x12): array-based, simple to implement and debug.
• Sliding piece attacks:
  • Precomputed attack tables or “magic bitboards” (compact hashing of occupancies to attack sets) to get rook/bishop/queen moves in O(1).
• Move encoding: from-square, to-square, flags (capture, promotion, castle, en passant), and optional score for ordering.
• Make/unmake or make/restore: apply a move to test legality and continue search, then revert; correctness and speed are critical.
• Move ordering (adjacent but related): once moves are generated, engines sort them (e.g., hash move, captures via MVV-LVA, killers, history) to improve alpha–beta pruning efficiency.

Testing correctness: perft

“Perft” (performance test) counts the number of leaf nodes by expanding all legal moves to a given depth. It is the standard unit test for move generators. Known reference counts include:

• Initial position perft: d1 = 20, d2 = 400, d3 = 8902, d4 = 197281, d5 = 4865609, d6 = 119060324.
• Kiwipete (r3k2r/p1ppqpb1/bn2pnp1/2P5/1p2P3/2N2N2/PPQ1BPPP/R3K2R w KQkq - 0 1): d1 = 48, d2 = 2039, d3 = 97862, d4 = 4085603, d5 = 193690690.

“Divide” is a perft variant that shows per-move child counts, helping pinpoint bugs (often in castling or en passant).

Examples

1) En passant legality trap: the pseudo-legal capture exd6 e.p. is illegal because it exposes White’s king to a rook on the e-file.

Position (White to move; en passant square d6). The move generator must reject 1. exd6 e.p. because after removing the pawn from e5, Black’s rook on e7 checks the king on e1.

2) Check evasions are restricted: in double check, only king moves are legal. For example, after a discovered check where a knight moves with a simultaneous bishop line-check, blocking is impossible — the generator must produce only king moves.

3) Human candidate move generation: from a typical middlegame, listing CCT (checks, captures, threats) first streamlines calculation. For instance, after 1. e4 e5 2. Nf3 Nc6 3. Bc4 Bc5, for White, checks include 4. Bxf7+; captures include 4. Nxe5; threats include 4. c3 followed by d4. A disciplined list reduces oversight.

Strategic and historical significance

• Claude Shannon (1950) framed the minimax search problem; practical engines rely on ultra-fast, correct move generation to explore game trees.
• Deep Blue (Kasparov vs. Deep Blue, 1997) evaluated hundreds of millions of positions per second, enabled by highly optimized generation and parallel search.
• Bitboards and magic move tables popularized in the 2000s gave a major speed boost, and remain standard in top engines.
• Modern engines like Stockfish achieve tens of millions of nodes per second on consumer hardware; a substantial portion of this throughput hinges on the move generator.

Interesting facts and common pitfalls

• Most generator bugs cluster around special rules: castling through check, en passant that reveals check, and promotion edge cases (especially underpromotions with capture).
• A tiny legality oversight can derail search, causing horizon effects or even illegal PVs (principal variations) in engine output.
• Static Exchange Evaluation (SEE) is often computed on top of generated capture moves to assess whether a capture “wins” or “loses” material before deeper search.

Quick checklist for robust move generation

• Generate fast pseudo-legal moves by piece type.
• Handle special moves (castling, en passant, promotions) with all conditions.
• Make and test: reject moves that leave your king in check (including the en passant removal effect).
• Validate with perft and divide on known test suites (start position, Kiwipete, tricky EP/castling positions).
• Profile and iterate: sliding attacks via magic bitboards or high-quality tables; prune generation when in check by generating only evasions.